#include "FindPrimeNum.h"
#include <stdlib.h>
#include <math.h>

int NormalFind_v0(char *isPrimeArr, int end)
{
    if(end < 2)
        return 0;
    int i, j, p = 0;
    for (i = 2; i <= end; ++i)
    {
        for (j = 2; j < i; ++j)
        {
            if( i % j == 0)
                break;
        }
        isPrimeArr[i] = i == j;
    }
    return p;
}

int E_Find(char *isPrimeArr, int range)
{
    if(range < 2)
        return 0;
    isPrimeArr[0] = isPrimeArr[1] = 0;
    int end = sqrt(range), res = range;
    for (int i = 2; i <= end; ++i)
    {
        if(!isPrimeArr[i]) 
            continue;
        for (int j = i * i; j <= range; j += i)
        {
            isPrimeArr[j] = 0;
            --res;
        }
    }
    return res;
}

//isPrimArr初始化全为1
int Euler_Find(char *isPrimeArr, int range, int* primeArr)
{
    isPrimeArr[0] = isPrimeArr[1] = 0;
    if(range < 2)
        return 0;
    int p = 0;
    for (int i = 2; i <= range; ++i)
	{
		if (isPrimeArr[i])
			primeArr[p++] = i;
		for (int j = 0; j < p; ++j)
		{
			int k = i * primeArr[j];
			if (k > range)
				break;
			isPrimeArr[k] = 0;
			if (i % primeArr[j] == 0)
				break;
		}
	}
    return p;
}
